/**
 * Created with IntelliJ IDEA.
 * Description:数组+链表,数组和链表都是节点类型,而节点有是map的键值对类型
 * User: lenovo
 * Date: 2023-02-23
 * Time: 17:52
 */
public class HashBuck {
    //对节点的定义
    //节点类:map键值对类型的节点
    public static class Node{
        int key;
        int val;
        //链表的next域
        Node next;
//节点类的构造方法
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }


    //数组
    Node[] array;
    //记录哈希桶有效数据的个数
    int usedSize;

    //默认的负载因子
    public static final float   DEFAULT_LOAD_FACTOR =0.75F;
//HashBuck的构造方法,初速化节点数组和哈希桶元素的有效个数
    public HashBuck() {
        this.array =new Node[10];
        this.usedSize = 0;
    }

    private float loadFactor(){
        //*1.0f:int转float 浮点数默认为double类型
        return usedSize*1.0f /array.length;

    }
    /**
     * 存储map节点
     * @param key
     * @param value
     * @return
     */
    public void putLast(int key,int value){
        //new出新节点
        Node node = new Node(key,value);
        //1.根据key定位到存放在数组的具体位置
        int index = key%array.length;
        //2.判读这个节点在是已经否存于数组下标对应的列表里
        Node cur = array[index];
        //array[index]是头结点,从头结点开始遍历
        //如果头结点为空
        if(cur == null){
            array[index] = node;
        }else{
            //while循环走到最后一个节点的时候结束
            while(cur.next != null){
                //有相同的元素,进行value值进行更新
                if(cur.key == key){
                    cur.val = value;
                }
                cur=cur.next;

            }
            //代码走到这里,cur停在最后一个节点位置处
            if(cur.key== key){
                cur.val = value;
            }else{
                //尾插
                cur.next = node;
            }

        }

        //哈希桶的计算器+1
        usedSize++;
        //检查负载因子
        if(loadFactor() >= DEFAULT_LOAD_FACTOR){
            //进行 扩容
            grow();
        }

    }
//扩容:2倍扩容
    private void grow() {
        Node[] newArray = new Node[array.length*2];
        //扩容之后,数组的长度变了,需要针对原数组里的每一个元素进行重新hash
        /**
         *Q:需要将原数组里的所有节点拷贝到扩容后的数组里吗?
         * A:不用,直接将原数组里的节点头插进扩容后的数组里
         * 1.遍历数组的每个每个链表
         * 2.每遍历到一个节点,就重新hash key%newArray.length
         * 3.找到index的位置直接进行头插法
         */
        for (int i = 0; i < array.length; i++) {
            if(array[i] != null){
                //开始遍历i位置处的链表
                Node cur = array[i];
                while(cur != null){
                    //记录一下原链表里cur后面的节点
                    Node curNext = cur.next;
                    //重新哈希
                    int index = cur.key% newArray.length;
                    //直接头插
                    cur.next = newArray[index];
                    newArray[index]=cur;
                    // cur.next = newArray[index];已将将原数组里链表cur后面的节点都丢掉
                    //cur = cur.next因此这样写不对;
                    //这样才对
                    cur = curNext;
                }

            }

        }


        this.array=newArray;
    }

    /**
     * 头插
     * @param key
     * @param value
     */
    public void putFront(int key,int value){
        //1.new出节点
        Node node = new Node(key,value);
        //2.hash函数找出key对应的下标
        int index = key%array.length;
        //3.查看链表里是否已经存在key,不存在就头插
        Node cur = array[index];
        while(cur != null){
            //存在就更新可以对应的value
            if(cur.key == key){
                cur.val = value;
                return;
            }
            //没找到就继续++
            cur=cur.next;
        }
        //循环走完说明没有找到,头插
        // array[index]就是数组的第一个元素也就是head头结点,也就是头结点
       node.next = array[index];
        array[index] = node;
        //插入成功,哈希桶计数器++
        usedSize++;
        /**
         * 代码走到这里,首先所有的节点都已经插入到没有扩容的数组里
         * 因此在扩容的时候,扩容的时候不需要再考虑key重复的情况,直接头插拿着找到的节点进行头插
         */
        //检查负载因子
        if(loadFactor() >= DEFAULT_LOAD_FACTOR){
            //进行 扩容
            grow();
        }



    }
    /**
     * 获取key对应的map节点
     */
    public int get(int key){
        //根据key通过hash获取到数组的下标位置
        int index = key%array.length;
        //从index的表头处开始遍历
        Node cur = array[index];
        while(cur != null){
            //找到了就返回value值
            if(cur.key == key){
                return cur.val;
            }
            cur = cur.next;
        }
        //没找到返回-1
        return -1;
    }
}
